//从1到n任选k个数字，求所有组合
//使用回溯算法，本质也是暴力穷举，但k个循环嵌套不能直接手写，于是回溯就可以写出来了
//回溯算法模板比较相似
#include<vector>
using std::vector;
//模板
void backtracking(int n,int k,int startIndex,vector<int>& path,vector<vector<int>>& result){      //设置起始点
    if(path.size()==k) {
        result.push_back(path);
        return;
    }   //终止条件

    for(int i=startIndex;i<=n;i++){ //for循环相当于横向遍历，遍历1到n的每一个数字
        path.push_back(i);
        backtracking(n,k,i+1,path,result);  //回溯递归是纵向遍历，相当于树的深度遍历
        path.pop_back();        //撤销处理结果，重要的回溯部分
    }
    //每一层回溯调用都有一个从i+1到n的for循环
}
vector<vector<int>> combine(int n, int k) {
    vector<int> path;
    vector<vector<int>> result;
    backtracking(n,k,1,path,result);
    return result;
}


//回溯的剪枝
//在for循环中，如果遇到path总数加起来不够result的情况，其实没有必要遍历，因此可以不去遍历
void backtracking_(int n,int k,int startIndex,vector<int>& path,vector<vector<int>>& result){      //设置起始点
    if(path.size()==k) {
        result.push_back(path);
        return;
    }   //终止条件
                        //修改的地方
    for(int i=startIndex;i<=n-(k-path.size())+1;i++){ //for循环相当于横向遍历，遍历1到n的每一个数字
        path.push_back(i);
        backtracking(n,k,i+1,path,result);  //回溯递归是纵向遍历，相当于树的深度遍历
        path.pop_back();        //撤销处理结果，重要的回溯部分
    }
    //每一层回溯调用都有一个从i+1到n的for循环
}








//进阶：从1-9取k个数，将总和为n的组合返回出来
//要记录的一个是当前总和，一个是path路径
//也可以进行剪枝

//递归的参数传递：什么参数需要在递归中传递，就要放进参数列表
void _backtracking(int n,int k,int sum,int startIndex,vector<int>& path,vector<vector<int>>& result){
    if(sum>n) return;   //剪枝，大于n就没必要再继续了
    if(path.size()==k&&sum==n) result.push_back(path);
                        //长度不够也不用继续了
    for(int i=startIndex;i<=9-(k-path.size())+1;i++){
        sum+=i;
        path.push_back(i);
        _backtracking(n,k,sum,i+1,path,result);              //作为递归积累的一部分，应将sum也放进参数列表里
        sum-=i;                                  //回溯，修改了什么就撤销什么
        path.pop_back();
    }
}
vector<vector<int>> combinationSum3(int k, int n) {
    vector<int> path;
    vector<vector<int>> result;
    _backtracking(n,k,0,1,path,result);
    return result;
}